package adapter;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.concurrent.*;
import java.util.function.Function;
import java.util.stream.Collectors;

/**
 * @功能
 * @创建时间 2020/5/3
 */
public class Adaptee {
    private static void printBoard(char[][] board) {
        for (int i = 0; i < 9; i++) {
            for (int j = 0; j < 9; j++) {
                System.out.print(board[i][j] + " ");
            }
            System.out.println();
        }
    }

    public static void main(String[] args) {
        char[][] board = new char[][]{
                {'5', '3', '.', '.', '7', '.', '.', '.', '.'},
                {'6', '.', '.', '1', '9', '5', '.', '.', '.'},
                {'.', '9', '8', '.', '.', '.', '.', '6', '.'},
                {'8', '.', '.', '.', '6', '.', '.', '.', '3'},
                {'4', '.', '.', '8', '.', '3', '.', '.', '1'},
                {'7', '.', '.', '.', '2', '.', '.', '.', '6'},
                {'.', '6', '.', '.', '.', '.', '2', '8', '.'},
                {'.', '.', '.', '4', '1', '9', '.', '.', '5'},
                {'.', '.', '.', '.', '8', '.', '.', '7', '9'}
        };

        printBoard(board);
        solveSudoku(board);
        printBoard(board);
    }
    static ExecutorService service = Executors.newSingleThreadExecutor();
    /**
     * 记录某行，某位数字是否已经被摆放
     */
    static boolean[][] row = new boolean[9][9];
    /**
     * 记录某列，某位数字是否已经被摆放
     */
    static boolean[][] col = new boolean[9][9];
    /**
     * 记录某 3x3 宫格内，某位数字是否已经被摆放
     */
    static boolean[][] block = new boolean[9][9];
    public static void solveSudoku(char[][] board){


        for (int i = 0; i < 9; i++) {
            for (int j = 0; j < 9; j++) {
                if (board[i][j] != '.') {
                    int num = board[i][j] - '1';
                    row[i][num] = true;
                    col[j][num] = true;
                    // blockIndex = i / 3 * 3 + j / 3，取整
                    block[i / 3 * 3 + j / 3][num] = true;
                }
            }
        }
        dfs(board,  0, 0);
    }

    private static boolean dfs(char[][] board, int i, int j) {
        while (board[i][j] != '.') {
            if (++j >= 9) {
                i++;
                j = 0;
            }
            if (i >= 9) {
                return true;
            }
        }
        for (int k = 0; k < 9; k++) {
            int blockIndex = i / 3 * 3 + j / 3;
            if (!row[i][k]
                    && !col[j][k ]
                    && !block[blockIndex][k]) {
                board[i][j] = (char)(k + '1');
                row[i][k] = true;
                col[j][k] = true;
                block[blockIndex][k] = true;
                if (dfs(board,  i, j)){
                    return true;
                } else {
                    row[i][k] = false;
                    col[j][k] = false;
                    block[blockIndex][k] = false;
                    board[i][j] = '.';
                }
            }

        }
        return false;
    }

    public static boolean searchRange(char[][] board) {
        char[] r1 = new char[10];
        char[] r2 = new char[10];
        char[] r3 = new char[10];
        char[] r4 = new char[10];
        char[] r5 = new char[10];
        char[] r6 = new char[10];
        char[] r7 = new char[10];
        char[] r8 = new char[10];
        char[] r9 = new char[10];

        char[] l1 = new char[10];
        char[] l2 = new char[10];
        char[] l3 = new char[10];
        char[] l4 = new char[10];
        char[] l5 = new char[10];
        char[] l6 = new char[10];
        char[] l7 = new char[10];
        char[] l8 = new char[10];
        char[] l9 = new char[10];

        char[] f1 = new char[10];
        char[] f2 = new char[10];
        char[] f3 = new char[10];
        char[] f4 = new char[10];
        char[] f5 = new char[10];
        char[] f6 = new char[10];
        char[] f7 = new char[10];
        char[] f8 = new char[10];
        char[] f9 = new char[10];
        for (int i = 0; i < board.length; i++) {
            char[] c = new char[10];
            char[] curr = board[i];
            for (int i1 = 0; i1 < curr.length; i1++) {

                int index = curr[i1] - '0';

                if (index != -2) {
                    if (c[index] != '1') {
                        c[index] = '1';
                    } else {
                        return false;
                    }

                if (i1 == 0) {
                    if (l1[index] != '1') {
                        l1[index] = '1';
                    } else {
                        return false;
                    }
                }
                if (i1 == 1) {
                    if (l2[index] != '1') {
                        l2[index] = '1';
                    } else {
                        return false;
                    }
                }
                if (i1 == 2) {
                    if (l3[index] != '1') {
                        l3[index] = '1';
                    } else {
                        return false;
                    }
                }
                if (i1 == 3) {
                    if (l4[index] != '1') {
                        l4[index] = '1';
                    } else {
                        return false;
                    }
                }
                if (i1 == 4) {
                    if (l5[index] != '1') {
                        l5[index] = '1';
                    } else {
                        return false;
                    }
                }
                if (i1 == 5) {
                    if (l6[index] != '1') {
                        l6[index] = '1';
                    } else {
                        return false;
                    }
                }
                if (i1 == 6) {
                    if (l7[index] != '1') {
                        l7[index] = '1';
                    } else {
                        return false;
                    }
                }
                if (i1 == 7) {
                    if (l8[index] != '1') {
                        l8[index] = '1';
                    } else {
                        return false;
                    }
                }
                if (i1 == 8) {
                    if (l9[index] != '1') {
                        l9[index] = '1';
                    } else {
                        return false;
                    }
                }
                if (i < 3) {
                    if (i1 < 3) {
                        if (f1[index] != '1') {
                            f1[index] = '1';
                        } else {
                            return false;
                        }
                    }
                    if (i1 < 6 && i1 >= 3) {
                        if (f2[index] != '1') {
                            f2[index] = '1';
                        } else {
                            return false;
                        }
                    }

                    if ( i1 >= 6) {
                        if (f3[index] != '1') {
                            f3[index] = '1';
                        } else {
                            return false;
                        }
                    }
                }
                if (i >= 3 && i < 6) {
                    if (i1 < 3) {
                        if (f4[index] != '1') {
                            f4[index] = '1';
                        } else {
                            return false;
                        }
                    }
                    if (i1 < 6 && i1 >= 3) {
                        if (f5[index] != '1') {
                            f5[index] = '1';
                        } else {
                            return false;
                        }
                    }

                    if ( i1 >= 6) {
                        if (f6[index] != '1') {
                            f6[index] = '1';
                        } else {
                            return false;
                        }
                    }
                }
                if (i >= 6) {
                    if (i1 < 3) {
                        if (f7[index] != '1') {
                            f7[index] = '1';
                        } else {
                            return false;
                        }
                    }
                    if (i1 < 6 && i1 >= 3) {
                        if (f8[index] != '1') {
                            f8[index] = '1';
                        } else {
                            return false;
                        }
                    }

                    if ( i1 >= 6) {
                        if (f9[index] != '1') {
                            f9[index] = '1';
                        } else {
                            return false;
                        }
                    }
                }
                }

            }
        }

        return true;
    }
    public static void main1(String[] args) {
        char[] ww = new char[9];
        System.err.println();
        int[] arr = {2,2};
        int[] arr1 = arr;
        arr1[0] = 1;
        System.err.println(arr[0]);
        System.err.println(arr1[0]);
//        System.err.println(searchRange(arr,2));
//        try {
//            int i = 2/ 0;
//            System.err.println(2);
//
//        }catch (Exception e){
//
//        }
//        List<String> a = new ArrayList(){{
//            add("1");
//            add("2");
//        }};
//        List<Future<String>> futures = a.stream().map(s -> service.submit(()-> "100")).collect(Collectors.toList());
//        futures.stream().forEach(s-> {
//            try {
//                System.err.println(s.get());
//            } catch (InterruptedException e) {
//                e.printStackTrace();
//                throw new RuntimeException(e);
//            } catch (ExecutionException e) {
//                e.printStackTrace();
//                throw new RuntimeException(e);
//            }
//        });
//        System.err.println(3);
    }
    public static int search(int[] nums, int target) {
        int startIndex = 0;
        int endIndex = nums.length - 1;
        int maxIndex = nums.length - 1;
        int midIndex1 = startIndex + (endIndex - startIndex) / 2;
            // 双增
            if (nums[startIndex] > nums[endIndex]
            && ((nums[midIndex1] < nums[endIndex] && nums[midIndex1] < nums[startIndex])
            || (nums[midIndex1] >nums[startIndex] && nums[midIndex1] > nums[endIndex]))) {
                if (nums[endIndex] >= target) {
                    while (startIndex < endIndex) {
                        int midIndex = startIndex + (endIndex - startIndex) / 2;
                        if (nums[midIndex] <= nums[maxIndex]) {
                            if (target > nums[midIndex]) {
                                startIndex = midIndex + 1;
                            } else if (target < nums[midIndex]) {
                                endIndex = midIndex - 1;
                            } else {
                                return midIndex;
                            }
                        } else {
                            startIndex = midIndex + 1;
                        }
                        if (startIndex == endIndex && target == nums[startIndex]) {
                            return startIndex;
                        }
                    }
                }else {
                    while (startIndex < endIndex) {
                        int midIndex = startIndex + (endIndex - startIndex) / 2;
                        if (nums[midIndex] > nums[maxIndex]) {
                            if (target < nums[midIndex]) {
                                endIndex = midIndex - 1;
                            } else if (target > nums[midIndex]) {
                                startIndex = midIndex  + 1;
                            } else {
                                return midIndex;
                            }
                        } else {
                            endIndex = midIndex - 1;
                        }
                        if (startIndex == endIndex && target == nums[startIndex]) {
                            return startIndex;
                        }
                    }
                }

            } else if (nums[startIndex] < nums[endIndex]
            && ((nums[midIndex1] < nums[startIndex] && nums[midIndex1] < nums[endIndex])
                    || (nums[midIndex1] > nums[startIndex] && nums[midIndex1] > nums[endIndex]))){
                if (target > nums[startIndex]) {
                    while (startIndex < endIndex) {
                        int midIndex = startIndex + (endIndex -startIndex) / 2;
                        if (nums[midIndex] > nums[0]) {
                            if (target < nums[midIndex]) {
                                startIndex = midIndex + 1;
                            } else if (target > nums[midIndex]) {
                                endIndex = midIndex - 1;
                            } else {
                                return midIndex;
                            }
                        } else {
                            startIndex = midIndex + 1;
                        }
                        if (startIndex == endIndex && target == nums[startIndex]) {
                            return startIndex;
                        }
                    }
                } else {
                    while (startIndex < endIndex) {
                        int midIndex = startIndex + (endIndex -startIndex) / 2;
                        if (nums[midIndex] <= nums[0]) {
                            if (target > nums[midIndex]) {
                                endIndex = midIndex - 1;
                            } else if (target < nums[midIndex]) {
                                startIndex = midIndex + 1;
                            } else {
                                return midIndex;
                            }
                        } else {
                            endIndex = midIndex - 1;
                        }
                        if (startIndex == endIndex && target == nums[startIndex]) {
                            return startIndex;
                        }
                    }
                }
            } else if (nums[startIndex] < nums[endIndex]){
                while (startIndex < endIndex) {
                    int midIndex = startIndex + (endIndex - startIndex) / 2;
                    if (nums[midIndex] > target) {
                        endIndex = midIndex - 1;
                    } else if (nums[midIndex] < target) {
                        startIndex = midIndex + 1;
                    }else {
                        return midIndex;
                    }
                    if (startIndex == endIndex && target == nums[startIndex]) {
                        return startIndex;
                    }
                }
            }else {
                while (startIndex < endIndex) {
                    int midIndex = startIndex + (endIndex - startIndex) / 2;
                    if (nums[midIndex] > target) {
                        startIndex = midIndex + 1;
                    } else if (nums[midIndex] < target) {
                        endIndex = midIndex - 1;
                    }else {
                        return midIndex;
                    }
                    if (startIndex == endIndex && target == nums[startIndex]) {
                        return startIndex;
                    }
                }
            }
        if (startIndex == endIndex && target == nums[startIndex]) {
            return startIndex;
        }

        return -1;
    }

    public static int wew (String s) {
        int[] dp = new int[300001];
        char[] sArr = s.toCharArray();
        for (int i = 1; i < sArr.length; i++) {
            if (sArr[i] == ')') {
                if (sArr[i - 1] == '(') {
                    if (i == 1) {
                        dp[i] = 2;
                    } else {
                        dp[i] = 2 + dp[i - 2];
                    }
                } else {
                    if (i - dp[i - 1] > 0 && sArr[i - dp[i - 1] - 1] == '(' && i > 1) {
                        if (i -dp[i - 1] == 1) {
                            dp[i] = dp[i - 1] + 2;
                        } else if (i -dp[i - 1] > 1) {
                            dp[i] = dp[i - 1] + 2 + dp[i - dp[i - 1] - 2];
                        }
                    }
                }
            }
        }
        return Arrays.stream(dp).max().getAsInt();
    }

    public  void request() {
        System.out.println("咳哟大众");
    }
}
